﻿//76. 最小覆盖子串
//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
//如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

class Solution
{
public:
    unordered_map<char, int> _s;
    unordered_map<char, int> _t;

    bool check()
    {
        for (auto& e : _t)
        {
            if (_s[e.first] < e.second)
            {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t)
    {
        for (auto& e : t)
        {
            _t[e]++;
        }

        int left = 0, right = -1;
        int len = INT_MAX, anyleft = -1, anyright = -1;
        int n = s.size();
        for (right = 0; right < n; right++)
        {
            _s[s[right]]++;
            while (check() && left <= right)
            {
                int temp = right - left + 1;
                if (temp < len)
                {
                    len = temp;
                    anyleft = left;
                }
                _s[s[left]]--;
                left++;
            }
        }
        return anyleft == -1 ? string() : s.substr(anyleft, len);
    }
};